package com.hdu.point_offer;

public class lcr130 {
    class Solution {

        int ROW;
        int COL;
        boolean[][] used;
        int cnt;

        public int wardrobeFinishing(int m, int n, int cnt) {
            this.ROW = m;
            this.COL = n;
            this.cnt = cnt;
            used = new boolean[ROW][COL];
            return f(0, 0);
        }


        int f(int row, int col)
        {
            if (!valid(row, col)) return 0;
            used[row][col] = true;
            return 1 + f(row + 1, col) + f(row, col + 1);
        }

        boolean valid(int row, int col)
        {
            return row >= 0 && row < ROW && col >= 0 && col < COL && !used[row][col] && sum(row) + sum(col) <= cnt;
        }

        int sum(int n)
        {
            int sum = 0;
            while (n > 0)
            {
                sum += n % 10;
                n /= 10;
            }
            return sum;
        }
    }
}
